This page was automatically generated by NetLogo 5.0RC4.
The applet requires Java 5 or higher. Java must be enabled in your browser settings. Mac users must have Mac OS X 10.4 or higher. Windows and Linux users may obtain the latest Java from Sun's Java site.
In order for this to work, this file, your model file (Random Binary DisCSP Generator(5RC4).nlogo), and the file NetLogoLite.jar must all be in the same directory. (You can copy NetLogoLite.jar from the directory where you installed NetLogo.)
On some systems, you can test the applet locally on your computer before uploading it to a web server. It doesn't work on all systems, though, so if it doesn't work from your hard drive, please try uploading it to a web server.
You don't need to include everything in this file in your page. If you want, you can just take the HTML code beginning with <applet> and ending with </applet>, and paste it into any HTML file you want. It's even OK to put multiple <applet> tags on a single page.
If NetLogoLite.jar and your model are in different directories, you must modify the archive= and value= lines in the HTML code to point to their actual locations. (For example, if you have multiple applets in different directories on the same web server, you may want to put a single copy of NetLogoLite.jar in one central place and change the archive= lines of all the HTML files to point to that one central copy. This will save disk space for you and download time for your users.)
powered by NetLogo
view/download model file: Random Binary DisCSP Generator(5RC4).nlogo
Title: Uniform Random Binary DisCSP Generator
Author: Ionel Muscalagiu, Jose M. Vidal
Description:
This is the implementation of the uniform Random Binary DisCSP generator.
The randomly generated (binary) CSPs are characterised by the 4-tuple (n, m,p1,p2),
where n is the number of variables, m is the uniform domain size, p1 is the portion of
the n * (n - 1) /2 possible constraints in the graph, and p2 is the portion of the m*m value pairs in each constraint that are disallowed by the constraint. That is, p1 may be thought of as the density of the constraint graph, and p2 as the tightness of constraints.
In generating a CSP (n, m,pl ,p2) exactly p1 * n * (n - 1)/2 constraints are randomly
selected (rounded to the nearest integer), and for each constraint selected exactly p2 * m*m conflicting pairs of values are selected (again, rounded to the nearest integer).
We implement and generated in NetLogo both solvable and unsolvable randomly generated
DisCSPs. These problems had one variable per agent so all constraints are between variables belonging to different agents (inter-agent constraints).
We implement in NetLogo a random instance generators in two steps:
Step1: We select with repetition t = p1 n/(n-1) random constraints. Each random
constraint is formed by selecting without repetition 2 of n variables.
Step2: For each constraint we uniformly select without repetition q = p2 m*m incompatible tuples of values, i.e. each constraint relation contains
exactly 1 -p2*m*m compatible tuples of values.
The random instance can be saved in file. The file-list has the following format:
Line 1: number-of-variables “ ” number-of-values “ ” p1-network-connectivity “ ” p2-constraint-tightness
Line 2- Line t : edges (constraints)
Next n line: List of incompatible tuples of values
;Uniform Random Binary DisCSP Genrator
; by Ionel Muscalagiu ( mionel@fih.utt.ro )
; Jose M. Vidal
;The randomly generated (binary) CSPs are characterised by the 4-tuple (n, m,p1,p2),
;where n is the number of variables, m is the uniform domain size, p1 is the portion of
;the n * (n - 1) /2 possible constraints in the graph, and p2 is the portion of the m*m value
;pairs in each constraint that are disallowed by the constraint. That is, p1 may be thought
;of as the density of the constraint graph, and p2 as the tightness of constraints.
;In generating a CSP (n, m,pl ,p2) exactly p1 * n * (n - 1)/2 constraints are randomly
;selected (rounded to the nearest integer), and for each constraint selected exactly p2 * m*m conflicting pairs of values are selected (again, rounded to the nearest integer).
;
breed [ nodes ]
breed [ edges ]
breed [ weights ]
;nodes = agents =variables
;each undirected edge goes from a to b
edges-own [a b weight-a weight-b wa-turtle wb-turtle number-of-edges ]
weights-own [sw1 sw2]
;links list of neighbor nodes (but links is a list of the 'who' of all nodes that have a constraint with me)
;the-neighbors the same but as an agentset
;neighbors-list is a list of the initial neighbors nodes
nodes-own [the-links neighbors-list the-neighbors Forbidden_Pairs colorn]
globals [x-max y-max diam friction tot-edges filename tick1 stoptick init-power-edges domain-color-list
total-conflict-pairs]
to setup-globals ; separate procedure for setting globals
let i 0
let max-edges 0
set diam 4
set tick1 0
set stoptick -2 ; set to some number to stop, generally for image collections
set x-max max-pxcor - (diam / 2) + 1; 0.5
set y-max max-pycor - (diam / 2) + 1; 0.5
set filename "" ; change to collect images (or just use command center after setup)
set-default-shape nodes "circle"
set-default-shape edges "line"
set friction .25
set init-power-edges 2
set max-edges round (number-of-variables * (number-of-variables - 1 ) / 2)
set tot-edges round (max-edges * p1-network-connectivity)
if tot-edges < number-of-variables - 1
[
set p1-network-connectivity precision ((number-of-variables - 1) / max-edges) 1
set tot-edges number-of-variables - 1
]
set domain-color-list []
set i 0
while [i < number-of-values][
set domain-color-list lput item i [15 105 64 125 45 85 35 55 5 12] domain-color-list
set i i + 1
]
end
to setup ; Setup the model for a run, build a graph.
;; (for your model to work with NetLogo's new plotting features,
;; __clear-all-and-reset-ticks should be replaced with clear-all at
;; the beginning of your setup procedure and reset-ticks at the end
;; of the procedure.)
__clear-all-and-reset-ticks
file-close
clear-output
set-default-shape weights "none"
setup-globals
setup-patches
setup-turtles
setup-random-binary-problems
graph-edges
end
to setup-patches
ask patches [set pcolor white]
end
to setup-turtles
create-nodes number-of-variables [
set color one-of domain-color-list
;set color item (random-int-or-float number-of-values) domain
set colorn position color domain-color-list
set label-color black
set size diam
set the-links []
set label who
setxy random-float (x-max) * (2 * (random 2) - 1)
random-float (y-max) * (2 * (random 2) - 1)
]
end
to setup-random-binary-problems ; Build a random binary CSP
let t 0
let t1 0
let g 0
let p1 0
let p2 0
let el 0
let i 0
let pos 0
let temp 0
let pos1 0
set g (list turtle 1)
while [length g < number-of-variables] [
set t1 one-of nodes with [not member? self g]
set t item random length g g
ask t1 [connect-edge t]
set g subgraph turtle 1
]
while [count edges < tot-edges] [
set t one-of nodes
set t1 one-of nodes with [self != t and not member? t the-links]
if t1 != nobody [ask t1 [connect-edge t]]
]
show count edges
ask nodes [
set the-neighbors nodes with [member? self ([the-links] of myself)]
set neighbors-list []
]
ask nodes[
ask the-neighbors
[
set neighbors-list lput [who] of myself neighbors-list
set neighbors-list sort neighbors-list
]
]
set total-conflict-pairs round(p2-constraint-tightness * (number-of-values ) * (number-of-values ))
show "Total-conflict-pairs " show total-conflict-pairs
ask nodes
[
without-interruption[
set Forbidden_Pairs get-list number-of-variables [];length(neighbors-list) []
foreach neighbors-list
[
if ? < who
[ set i 0
while [i < total-conflict-pairs]
[
set p1 random number-of-values
set p2 random number-of-values
set el list p1 p2
set pos ?
if not member? el item pos Forbidden_Pairs
[
set temp lput el (item pos Forbidden_Pairs)
set Forbidden_Pairs replace-item pos Forbidden_Pairs temp
set i i + 1 ]
]
]
; set pos pos + 1
]
]
]
end
to WriteGraf
let sir 0
let i 0
let pos 0
let cc 0
let per 0
file-close
let fis "graph.txt"
file-close
if (file-exists? fis )
[file-delete fis]
file-open fis
set total-conflict-pairs round(p2-constraint-tightness * (number-of-values ) * (number-of-values ))
file-print (word number-of-variables " " number-of-values " " ( 2 * tot-edges) " " total-conflict-pairs)
ask nodes[
ask the-neighbors
[
set cc [who] of myself
file-print (word cc " " who )]
]
file-close
set fis "int.txt"
file-close
if (file-exists? fis )
[file-delete fis]
file-open fis
ask nodes
[
without-interruption[
set pos 0
set cc [who] of myself
set pos 0
; show Forbidden_Pairs
; show neighbors-list
foreach neighbors-list
[
if ? < who
[ set i 0
file-print (word cc " " ? " " length item ? Forbidden_Pairs)
foreach item ? Forbidden_Pairs
[
set per ?
foreach per
[file-type ?
file-type " "]
]
file-print ""
]
]
]
]
file-close
end
to WriteGrafList
let sir 0
let i 0
let pos 0
let cc 0
let fis "graph-list.txt"
file-close
if (file-exists? fis )
[file-delete fis]
file-open fis
file-print (word number-of-variables " " number-of-values " " p1-network-connectivity " " p2-constraint-tightness)
ask nodes[
ask the-neighbors
[
set cc [who] of myself
file-print (word cc " " who )]
]
ask nodes
[
without-interruption[
set pos 0
set cc [who] of myself
; print cc
file-print cc
file-print Forbidden_Pairs
]
]
file-close
end
to LoadGraf
let sir 0
let i 0
let dens 0
let edges-created 0
let t 0
let t1 0
let cc 0
let max-edges 0
let temp []
let tp []
file-close
let fis "graph.txt"
file-open fis
set number-of-variables file-read
set number-of-values file-read
set p1-network-connectivity file-read
set p2-constraint-tightness file-read
;; (for your model to work with NetLogo's new plotting features,
;; __clear-all-and-reset-ticks should be replaced with clear-all at
;; the beginning of your setup procedure and reset-ticks at the end
;; of the procedure.)
__clear-all-and-reset-ticks
clear-output
set-default-shape weights "none"
setup-globals
setup-patches
setup-turtles
ask nodes [
set the-links []
set neighbors-list []
]
show (word number-of-variables " " number-of-values " " p1-network-connectivity " " p2-constraint-tightness)
set max-edges round (number-of-variables * (number-of-variables - 1 ) / 2)
set tot-edges round (max-edges * p1-network-connectivity)
set total-conflict-pairs round(p2-constraint-tightness * (number-of-values ) * (number-of-values ))
set edges-created 0
while [edges-created < 2 * tot-edges]
[
set t file-read
set t1 file-read
if not member? turtle t1 [the-links] of turtle t and not member? turtle t [the-links] of turtle t1
[ask turtle t1 [connect-edge turtle t ]
ask turtle t [
set neighbors-list lput t1 neighbors-list
]
ask turtle t1 [
set neighbors-list lput t neighbors-list ]
]
set edges-created edges-created + 1
]
ask nodes [
set the-neighbors nodes with [member? self ([the-links] of myself)]
]
set i 1
while [i <= number-of-variables]
[
set cc file-read
set temp file-read
ask turtle cc [set Forbidden_Pairs temp]
set i i + 1
]
file-close
end
to-report subgraph [n] ; report the complete connected subgraph containing n1
let stack 0
let graph 0
set graph (list n)
set stack (list n)
while [length stack > 0] [
foreach [the-links] of first stack [
if not member? ? graph [
set graph lput ? graph
set stack lput ? stack
]
]
set stack but-first stack
]
report graph
end
; The run procedure which makes the model take one step.
; It moves the nodes so that we get a better layout. You can also click on a node and move it by hand.
to go
let t 0
if filename = 0 [setup] ; an attempt to work even tho user forgets setup
if stoptick = -1 [stop]
no-display
step
display
if mouse-down? [
set t closest-xy mouse-xcor mouse-ycor nodes ;
while [mouse-down?] [
ask t [setxy mouse-xcor mouse-ycor]
no-display
ask edges with [a = t or b = t][adjust-edge]
step
display
]
]
;check-movie
if stoptick = tick1 [stop]
end
to step ; Adjust the edges and nodes for one step of the model
let delta 0
without-interruption [
ask edges [
set delta (spring-force * (size - spring-length)) / 2.0
ask a [set heading towards-nowrap [b] of myself jump-nowrap delta]
ask b [set heading towards-nowrap [a] of myself jump-nowrap delta]
]
ask nodes [
ask nodes with [self != myself] [
set delta distance-nowrap myself
set delta mutual-repulsion / (delta * delta)
set heading towards-nowrap myself
jump-nowrap (- delta)
]
]
ask edges [adjust-edge]
]
end
;;;; Edge & Node utilities
to connect-edge [other-node] ; node proc: attach an edge between self and other
hatch 1 [
set breed edges
set a myself
set b other-node
set weight-a 1
set weight-b 1
hatch 1 [
set breed weights
;set ([wa-turtle] of myself) self
set sw1 myself
ask sw1 [set wa-turtle self]
set label ([weight-a] of myself)]
hatch 1 [
set breed weights
;set ([wb-turtle] of myself) self
set sw2 myself
ask sw2 [set wb-turtle self]
set label ([weight-b] of myself)]
ask a [set the-links lput [b] of myself the-links]
ask b [set the-links lput [a] of myself the-links]
set color black
set label ""
adjust-edge
]
end
to-report sign [num]
ifelse num < 0 [report -1][report 1]
end
to-report closest-xy [x y agent-set] ; Return closest agent to x, y
report min-one-of agent-set [distancexy-nowrap x y]
end
to jump-nowrap [dist] ; turtle proc: jump but don't wrap, bounce w/ friction instead
let x 0
let y 0
set x xcor + dist * dx
set y ycor + dist * dy
if (abs x) > x-max [set x sign x * (x-max - (1 - friction) * ((abs x) - x-max))]
if (abs y) > y-max [set y sign y * (y-max - (1 - friction) * ((abs y) - y-max))]
setxy x y
end
to adjust-edge ; edge proc: reattach to a & b nodes
setxy [xcor] of b [ycor] of b
set heading towards-nowrap a
fd diam / 2 + 1
;set ([xcor] of wb-turtle) xcor
ask wb-turtle [ set xcor [xcor] of myself ]
;set ([ycor] of wb-turtle) ycor
ask wb-turtle [ set ycor [ycor] of myself ]
setxy [xcor] of a [ycor] of a
set size distance-nowrap b - diam
set heading towards-nowrap b
fd diam / 2 + 1
;set ([xcor] of wa-turtle) xcor
ask wa-turtle [ set xcor [xcor] of myself ]
;set ([ycor] of wa-turtle) ycor
ask wa-turtle [ set ycor [ycor] of myself ]
setxy [xcor] of a [ycor] of a
jump (size / 2) + (diam / 2)
end
to-report make-list [num element]
let i 0
let result 0
set i 0
set result []
while [i < num] [
set result lput element result
set i i + 1
]
report result
end
to-report copy-list [l]
let r 0
set r []
foreach l [
set r lput ? r]
report r
end
; n is length of list
; el is the element
to-report get-list [n el]
let i 0
let lst 0
set i 0
set lst []
while [i < n] [
set lst fput el lst
set i i + 1]
report lst
end
to graph-edges ; Make a simple edge histogram
set-current-plot "edge-distribution"
set-plot-x-range 1 1 + max [length the-links] of nodes
histogram [length the-links] of nodes
end